﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution200
{
    //DFS
    public int NumIslands2(char[][] grid)
    {
        int sum = 0;
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[0].Length; j++)
            {
                if (grid[i][j] == '1')
                {
                    sum++;
                    //把相邻的1全部设置为0 
                    DFS(i, j, grid);

                }



            }


        }
        return sum;



    }

    private void DFS(int row, int col, char[][] grid)
    {
        grid[row][col] = '0';

        //右
        if (col < grid[0].Length - 1 && grid[row][col + 1] == '1')
        {

            DFS(row, col + 1, grid);
        }

        //下
        if (row < grid.Length - 1 && grid[row + 1][col] == '1')
        {

            DFS(row + 1, col, grid);
        }

        //左
        if (col > 0 && grid[row][col - 1] == '1')
        {

            DFS(row, col - 1, grid);
        }
        //上
        if (row > 0 && grid[row - 1][col] == '1')
        {

            DFS(row - 1, col, grid);
        }

    }
    //BFS
    public int NumIslands(char[][] grid)
    {
        int sum = 0;
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[0].Length; j++)
            {
                if (grid[i][j] == '1')
                {
                    sum++;
                    //把相邻的1全部设置为0 
                    BFS(i, j, grid);

                }



            }


        }
        return sum;



    }
    public void BFS(int currow, int curcol, char[][] grid)
    {
        
  
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(currow);//x
        queue.Enqueue(curcol);//y

        while (queue.Count > 0)
        {
            int row = queue.Dequeue();//
            int col = queue.Dequeue();//

            //右
            if (col < grid[0].Length - 1 && grid[row][col + 1] == '1')
            {
                grid[row][col + 1] = '0';
                //入队
                queue.Enqueue(row);//x
                queue.Enqueue(col+1);//y
            }

            //下
            if (row < grid.Length - 1 && grid[row + 1][col] == '1')
            {

                grid[row + 1][col] = '0';
                //入队
                queue.Enqueue(row+1);//x
                queue.Enqueue(col);//y
            }

            //左
            if (col > 0 && grid[row][col - 1] == '1')
            {

                grid[row][col - 1] = '0';
                //入队
                queue.Enqueue(row);//x
                queue.Enqueue(col-1);//y
            }
            //上
            if (row > 0 && grid[row - 1][col] == '1')
            {

                grid[row - 1][col] = '0';
                //入队
                queue.Enqueue(row-1);//x
                queue.Enqueue(col);//y
            }
        }





      



    }

}

class Program200
{
    static void Main200(string[] args)
    {
                    string[][] grid = [
               ["1", "1", "1", "1", "0"],
                        ["1", "1", "0", "1", "0"],
                        ["1", "1", "0", "0", "0"],
                        ["0", "0", "0", "0", "0"]
             ];
                    char[][] grids = [
                ['1', '1', '1'],
                        ['1', '1', '0'],
                        ['1', '1', '0',],
                        ['0', '0', '0',]
              ];
        Solution200 solution = new Solution200();
        int res = solution.NumIslands(grids);
        Console.WriteLine(res);
    }
}
